package greddy;

import java.util.Arrays;
import java.util.Comparator;

public class _12_452_用最少数量的箭引爆气球 {
    public static int findMinArrowShots(int[][] points) {
    	// 根据每个元素的左边界从小到大进行排序，每一个左边界都会比前一个的左边界大
    	Arrays.sort(points, new Comparator() {
			@Override
			public int compare(Object o1, Object o2) {
				int[] i = (int[]) o1;
				int[] j = (int[]) o2;
				Integer a = i[0];
				Integer b = j[0];
				return a.compareTo(b);
			}	
    	});

    	int count = 1;
    	for(int i = 1; i < points.length; i++) {
    		// 当前的左边界大于前一个元素的右边界，说明不重合
    		if(points[i][0] > points[i-1][1]) {
    			count++;
			// 左边界在前一个元素范围内，说明有重合，则当前值的右边界要更新为两个元素右边界的最小值
    		// 更新完后，下一个元素又会继续跟当前更新完的元素进行比较判断
    		}else {
    			points[i][1] = Math.min(points[i][1], points[i-1][1]);
    		}
    	}
    	
    	
    	return count;
    }
    public static void main(String[] args) {
    	int[][] points = {{3,9},{7,12},{3,8},{6,8},{9,10},{2,9},{0,9},{3,9},{0,6},{2,8}};

    	System.out.println(findMinArrowShots(points));
	}
}
